package com.newcoder.alibaba;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Mook006 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int n = Integer.parseInt(br.readLine());
            String[] params = br.readLine().trim().split(" ");
            int[] weights = new int[n];
            for(int i = 0; i < n; i++) {
                weights[i] = Integer.parseInt(params[i]);
            }
            System.out.println(crossRiver(weights));
        }
    }

    private static int crossRiver(int[] weights) {
        Arrays.sort(weights);
        int n = weights.length;
        int totalTime = 0;
        while(n >= 4){
            /* 1.最轻的每次都将船开回来，每次载一个；
               2.最轻的两先过去，最轻的那个开船回来让最重的两个过去，那边轻的再把船开回来
            */
            totalTime += Math.min(weights[0]*2 + weights[n - 2] + weights[n - 1],
                    weights[0] + weights[1]*2 + weights[n - 1]);
            n -= 2;
        }
        // 还剩不到4人
        if(n == 3){
            totalTime += weights[0] + weights[1] + weights[2];
        }else{
            totalTime += weights[1];     // 最轻的两个快速过河
        }
        return totalTime;
    }
}
